package com.zql.JianZhiOffer;

import java.util.Arrays;

/**
 * 旋转数组中的最小数字
 * Created By ShuHua on 2022/5/3.
 */
public class Offer_11 {
    /**
     * 遍历求最小值
     * @param numbers
     * @return
     */
    public int minArray(int[] numbers) {
        int min=numbers[0];
        for (int i = 0; i < numbers.length; i++) {
            if(min>numbers[i])min=numbers[i];
        }
        return min;
    }

    /**
     * 使用二分法，时间复杂度为O(log2N)
     * @param numbers
     * @return
     */
    public static int minArray2(int[] numbers) {
        int left=0;
        int right=numbers.length-1;
        while (left<right){
            int mid = left+(right-left)/2;
            if(numbers[mid]>numbers[right]){
                //mid一定不是最小数字，因此可以排除mid
                left=mid+1;
            }else if(numbers[mid]==numbers[right]){
                //只能排除right
                right--;
            }else {
                //不能排除mid不是最小数
                right=mid;
            }
        }
        //因为循环的终止条件是right==left 所以这里返回哪个都是一样的
        return numbers[right];
    }

    public static void main(String[] args) {
        int[] a = {1,3,5};
        System.out.println(minArray2(a));
    }

}
